package com.demo.data.struct2.树.线索二叉树;

/**线索二叉树：

按照某种方式对二叉树进行遍历，可以把二叉树中所有结点排序为一个线性序列，在该序列中，除第一个结点外每个结点有且仅有一个直接前驱结点；除最后一个结点外每一个结点有且仅有一个直接后继结点；

在有N个节点的二叉树中需要利用N+1个空指针添加线索，这是因为在N个节点的二叉树中，每个节点有2个指针，所以一共有2N个指针，除了根节点以外，每一个节点都有一个指针从它的父节点指向它，所以一共使用了N-1个指针，所以剩下2N-(N-1)也就是N+1个空指针；

若能利用这些空指针域来存放指向该节点的直接前驱或是直接后继的指针，则可由此信息直接找到在该遍历次序下的前驱结点或后继结点，从而比递归遍历提高了遍历速度，节省了建立系统栈所使用的存储空间；

这些被重新利用起来的空指针就被称为线索（Thread），加上了这些线索的二叉树就是线索二叉树；

根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种；

记node指向二叉链表中的一个结点，以下是建立线索的规则：

    （1）如果node的左指针域为空，则存放指向某种遍历序列中该结点的前驱结点，这个结点称为node的前驱；

    （2）如果node的右指针域为空，则存放指向中序遍历序列中该结点的后继结点。这个结点称为node的后继；
 * @author zhangsulei
 *
 */
public class ThreadTreeTest
{
	public static void main(String[] args)
	{
		int[] data = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

		ThreadTree threadTree = new ThreadTree(data);      // 创建普通二叉树
		threadTree.inList(threadTree.getRoot());           // 中序递归遍历二叉树
		System.out.println();

		threadTree.inThread(threadTree.getRoot());         // 采用中序遍历将二叉树线索化
		threadTree.inThreadList(threadTree.getRoot());     // 中序遍历线索化二叉树
	}

}